Trie 1[入门]

无内鬼,来点入门级题目。
Trie就不讲了,只讲题。

一点无关紧要但是可能引起阅读障碍的点:
①tot的初值到底啥情况,怎么一会11一会00
答:tot的最开始的初值是根节点rootroot,具体在分配新的idid的时候,是用的前置++++,故最开始的tottot的初值是没有显明分配的,但是具体在TreiTrei的操作里初始的点位置必须是根节点,如果不对应会出错。一会11一会00是因为有些代码是我以前的,后来新写的时候没注意这个问题,不过不影响。
#define _CRT_SECURE_NO_WARNINGS是什么
答:关闭msvcmsvc的检查,不影响。

①Hdu 4825 Xor Sum
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4825
题目大意:给定一个nn个数的集合,一共有mm次询问,每次询问给出一个数xx,问在集合里与xx异或后结果最大的数是哪一个。
数据范围:
1N,M1051 \leq N,M \leq 10^5
所有正整数均在intint范围内。
分析:把所有的数看成是22进制数插入TrieTrie中,每次查询时如果有与当前xx的一个数位上相反的数字,就选择相反的,没有就只能退而求其次选择与这一位相同的。
不过本题是要输出原来的数字,故searchsearch时,如果当前走下去的那一位是11的话,就把resres里的这一个数位调整成1,最后输出resres即可。
代码:

using namespace std;

const int N = 1e5+7;
int trie[N*32][2],tot = 1,tar[N * 32];
int a[N];
void insert(int a)
{
    int p = 1;
    for(int i = 31;i >= 0;--i)
    {
        int ch = a >> i & 1;
        if(!trie[p][ch])    trie[p][ch] = ++tot;
        p = trie[p][ch];
    }
    tar[p] = a;
}
int search(int x)
{
    int p = 1,res = 0;
    for(int i = 31;i >= 0;--i)
    {
        int ch = x >> i & 1;
        if(trie[p][ch ^ 1])	p = trie[p][ch ^ 1],res += (!ch) ? (1 << i) : 0;
        else p = trie[p][ch],res += (ch) ? (1 << i) : 0;
    }
    return tar[p];
}
int main()
{
	int T;scanf("%d",&T);
	for(int _ = 1;_ <= T;++_)
	{
		memset(trie,0,sizeof trie);
		memset(tar,0,sizeof tar);
		tot = 1;
		printf("Case #%d:\n",_);
		int n,m;scanf("%d%d",&n,&m);
	    for(int i = 0;i < n;++i)
	    {
	        scanf("%d",&a[i]);
	        insert(a[i]);
	    }
	    for(int i = 0;i < m;++i)
	    {
	    	int x;scanf("%d",&x);
	    	printf("%d\n",search(x));
	    }
	}

    return 0;
}

②Hdu 5536 Chip Factory
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5536
题目大意:给定一个nn个数的集合{a}\{a\},求下式

maxij,jk,ki(ai+aj)(ak)\max\limits_{i \neq j ,j \neq k,k \neq i} (a_i + a_j) \bigoplus (a_k)

数据范围:
3n10003 \leq n \leq 1000
0ai1090 \leq a_i \leq 10^9
分析:
题目意思就是在集合里选出三个数,求一下两个和和另外一个数的异或。这个题很显然就不能像上面那样直接去把所有数丢进TrieTriesearchsearch推答案了,但是呢由于nn很小,所以时间上允许我们枚举每个数对丢到TrieTrie里查找答案,故一个比较直接的想法就是想办法实现在TrieTrie中删除掉某个字符串。先把所有单个的数aia_i加入TrieTrie,再枚举所有数对的时候,先把数对里的两个数从TrieTrie里删除,再查询两者的和在TrieTrie里最大的结果具体是多少。
现在来考虑怎么删除掉TrieTrie中的一个字符串。很显然直接把TrieTrie里的下标,或者说指针的指向给他删掉是不可取的,可以采取标记的措施:对每个分配了位置的具体的节点,加一个cntcnt记录他一共有几次被使用上了,insertinsert的时候就+1+1deletedelete的时候就1-1。最后在具体searchsearch的时候,不光要看下一个节点是否存在,还要看下一个点的具体cntcnt是不是大于00的。
本题范围有点大,记得开llll
代码:

using namespace std;
typedef long long ll;
#define int ll 
const int N = 2007;
int tr[N * 32][2],cnt[N * 32],tot,val[N * 32];
int n,a[N];
void insert(int x,int v)
{
	int p = 0;
	for(int i = 32;i >= 0;--i)
	{
		int ch = x >> i & 1;
		if(!tr[p][ch])	tr[p][ch] = ++tot;
		cnt[tr[p][ch]] += v;
		p = tr[p][ch];
	}
	val[p] = x;
}
int search(int x)
{
	int p = 0;
	for(int i = 32;i >= 0;--i)
	{
		int ch = x >> i & 1;
		if(tr[p][ch ^ 1])	
		{
			if(cnt[tr[p][ch ^ 1]] > 0)
				p = tr[p][ch ^ 1];
			else
				p = tr[p][ch];
		}
		else
			p = tr[p][ch];
	}
	return val[p];
}
void update(int x,int v)
{
	int p = 0;
	for(int i = 32;i >= 0;--i)
	{
		int ch = x >> i & 1;
		cnt[tr[p][ch]] += v;
		p = tr[p][ch];
	}
}
signed main()
{
	int T;scanf("%lld",&T);
	while(T--)
	{
		memset(tr,0,sizeof tr);
		memset(val,0,sizeof val);
		memset(cnt,0,sizeof cnt);
		tot = 0;
		scanf("%lld",&n);
		for(int i = 1;i <= n;++i)	scanf("%lld",&a[i]),insert(a[i],1);
		int res = 0;
		for(int i = 1;i <= n;++i)
		{
			for(int j = i + 1;j <= n;++j)
			{
				update(a[j],-1);update(a[i],-1);
				res = max(res,search(a[i] + a[j]) ^ (a[i] + a[j]));
				update(a[j],1);update(a[i],1);
			}
		}
		printf("%lld\n",res);
	}


    return 0;
}

③洛谷4551 最长异或路径
原题链接:https://www.luogu.com.cn/problem/P4551
题目大意:给定一颗nn个节点的树,下标从11nn。在树上找到两个不同的节点求最长的异或路径,即经过的路径上的所有权值的异或和。
分析:
如果说这个题不是异或和,而是普通的加和,我们很容易想到应该是合并两两段最大的往下的路径和。但是异或很显然是没有说两个最大的结果异或起来是最大的结果这样的特性,我们只能退而求其次。找到从根节点往下的所有节点的路径异或和,即求出一个D[x]D[x]rootrootxx的简单路径的异或和。之后相当于在树上找另外一个节点yy,使得D[x]D[y]D[x] \bigoplus D[y]的结果最大,这显然用TrieTrie就可以实现了。
而且在searchsearch的时候,其实不需要在意xyx \neq y的条件,一个是不可能只有D{x]自己,第二个是就算所有序列里都是D[x]D[x],这个时候查到的其他的yy虽然值与之相等但是不同的数,也不违反规则。
代码:

using namespace std;

const int N = 1e5+7,M = 2e6+7;
int trie[N*32][2],a[N],tot = 1;
int edge[M],cost[M],ver[M],succ[M],cnt;
void add(int u,int v,int w)
{
    edge[cnt] = v;
    cost[cnt] = w;
    succ[cnt] = ver[u];
    ver[u] = cnt++;
}
void dfs(int u,int fa,int sum)
{
    a[u] = sum;
    for(int i = ver[u];~i;i = succ[i])
    {
        int j = edge[i];
        if(j != fa) dfs(j,u,sum^cost[i]);
    }
}
void insert(int a)
{
    int p = 1;
    for(int i = 31;i >= 0;--i)
    {
        int ch = a >> i & 1;
        if(!trie[p][ch])    trie[p][ch] = ++tot;
        p = trie[p][ch];
    }
}
int search(int a)
{
    int res = 0,p = 1;
    for(int i = 31;i >= 0;--i)
    {
        int ch = a >> i & 1;
        if(trie[p][ch^1])
            res |= (1 << i),p = trie[p][ch^1];
        else p = trie[p][ch];
    }
    return res;
}

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    memset(ver,-1,sizeof(ver));
    int n;cin >> n;
    for(int i = 0;i < n-1;++i)
    {
        int u,v,w;cin >> u >> v >> w;
        --u;--v;
        add(u,v,w);
        add(v,u,w);
    }
    dfs(0,-1,0);
    int res = 0;
    for(int i = 0;i < n;++i)
        insert(a[i]);
    for(int i = 0;i < n;++i)
        res = max(res,search(a[i]));
    cout << res;
    return 0;
}